#include <stdio.h>
#include <stdlib.h>

typedef struct {
    char NES; // 生成式的左部，非终止符
    char str[20]; // 生成式的右式
    int len; // 生成式右部的长度
} Gen;
typedef struct {
    char ch; // 记录非终结符
    int mark; // 标志其是否为可终止非终结符
} Terminal;
#define NEND_MAX 10 // 非终结符最大数量
#define STR_MAX 100
// 判断一条产生式是否可以导出终止符串
/**
 * NEnd:非终止符集
 * sLen:非终止符数量
 * gen:一条生成式
*/
int judge(Terminal *NEnd, int sLen, Gen* gen)
{
    int i, j, mark = 1; // mark为0表示可以推出非终止符
    for (i = 0; i < gen->len; i++) { // 对产生式右部的每一个字符进行判断
        if (gen->str[i] == '|') {
            // 若该产生式可以推导出终止符，则不再检查|后面的产生式
            if (mark == 1)
                break;
            else
                mark = 1;
        }
        for (j = 0; j < sLen; j++) { // 每一个字符都和非终止符进行对比
            if (gen->str[i] == NEnd[j].ch && NEnd[j].mark == 0) {
                mark = 0;
            }
        }
    }
    for (i = 0; i < sLen && NEnd[i].ch != gen->NES; i++)
        ;
    if (mark == NEnd[i].mark)
        return 0; // 没有发生变动
    NEnd[i].mark = mark;
    return 1; // 发生过变动
}
// 获取不可终止非终止符，更新不可终止非终止的集合，返回改动标志
int getSet(Gen** gen, char* NEnd)
{
    int i, j;
}

// 遍历生成式集合，得到不可终止非终结符
Terminal *getEndSet(int* length)
{
    FILE* fp = NULL;
    fp = fopen("codes/pratice4.txt", "r");
    // 获取终止符集合
    int i = 0;
    char str[STR_MAX];
    Terminal *NEnd = (Terminal *)malloc(sizeof(Terminal)*NEND_MAX);
    fgets(str, STR_MAX, fp);
    int count = 0;
    for (i = 0; str[i] != '#'; i += 2) {
        NEnd[count].ch = str[i];
        NEnd[count++].mark = 0; // 初始时都不可推出终止符
    }
    *length = count;
    // 生成式集合格式化，包括长度，生成式右部，和生成式左部
    int len = 0; // len记录生成式的条数
    Gen* genSet[10];
    while (fp != NULL) {
        int index = 0;
        fgets(str, STR_MAX, fp);
        if (str[0] == '#')
            break; // 检测到文件终止符时结束循环
        Gen* newGen = (Gen*)malloc(sizeof(Gen));
        newGen->NES = str[0];

        while (str[index] != '>')
            index++;
        index++;
        count = 0;
        while (str[index] != '\n')
            newGen->str[count++] = str[index++];
        newGen->len = count;
        genSet[len] = newGen;
        len += 1;
    }

    //接下来确定生成式是否导出非终结符
    int change = 1, j;
    while (change == 1) {
        change = 0;
        for (j = 0; j < len; j++) {
            int flag = judge(NEnd, *length, genSet[j]);
            if (flag == 1)
                change = 1; // 发生改动
        }
    }

    return NEnd;
}

int main()
{
    int len;
    Terminal *Set = getEndSet(&len);
    int i;
    printf("不可终止非终结符：");
    for (i = 0; i < len; i++) {
        if(Set[i].mark == 0)
            printf("%c ", Set[i].ch);
    }
    return 0;
}